package org.example.Soution001;

import com.sun.xml.internal.ws.addressing.WsaActionUtil;

public class IsBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(32);
        root.left = new TreeNode(26);
        root.right = new TreeNode(47);
        root.left.left = new TreeNode(19);
        root.left.left.right = new TreeNode(27);
        root.right.right = new TreeNode(56);
        IsBST isBST = new IsBST();
        System.out.println(isBST.isValidBST(root));

    }

    public boolean isValidBST(TreeNode root) {
        if(root.left == null && root.right == null){
            return true;
        } else if(root.left == null && root.right != null){
            int[] right=minOrMax(root.right);
            return (right[0]>root.val)&&right[2]==1;
        }else if(root.left != null && root.right == null){
            int[] left=minOrMax(root.left);
            return (left[1]<root.val)&&left[2]==1;
        }else{
            int[] left=minOrMax(root.left);
            int[] right=minOrMax(root.right);
            return (left[1]<root.val)&&(right[0]>root.val)&&left[2]==1&&right[2]==1;
        }
    }

    //多加一个方法判断是否大于左子树最大值和小于右子树最小值
    public int[] minOrMax(TreeNode root) {
        //res[0]=min,res[1]=max,res[2]==1为BST，否则不为BST
        int[] res = new int[3];
        if(root.left == null && root.right == null){
            res[0] = root.val;res[1] = root.val;res[2] = 1;
        }else if(root.left == null && root.right != null){
            int[] right=minOrMax(root.right);
            res[0] = root.val;res[1] = right[1];
            if(root.val<right[0]&&right[2]==1){
                res[2]=1;
            }else{
                res[2]=0;
            }
        }else if(root.left != null && root.right == null){
            int[] left=minOrMax(root.left);
            res[0] = left[0];res[1] = root.val;
            if(root.val>left[1]&&left[2]==1){
                res[2]=1;
            }else{
                res[2]=0;
            }
        }else{
            int[] left=minOrMax(root.left);
            int[] right=minOrMax(root.right);
            res[0] =left[0];res[1]=right[1];
            if(root.val>left[1]&&root.val<right[0]&&left[2]==1&&right[2]==1){
                res[2]=1;
            }else{
                res[2]=0;
            }
        }
        return res;
    }
}
